//
// Created by Vincent_Vic on 2020/5/11.
//

#ifndef DATAORGANIZATION_CMAPBASE1_H
#define DATAORGANIZATION_CMAPBASE1_H
#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>
using namespace std;

class Node{
public:
    Node(char mData = 0) : mData(mData) { mIsVisited = false;}
    char mData; //节点数据
    bool mIsVisited;    //是否被访问过
};

class Edge{
public:
    Edge() {}

    Edge(int iNodeIndexA, int iNodeIndexB, int iWeightValue) : iNodeIndexA(iNodeIndexA), iNodeIndexB(iNodeIndexB),
                                                               iWeightValue(iWeightValue) {bSelected = false;}
    int iNodeIndexA;
    int iNodeIndexB;
    int iWeightValue;
    bool bSelected;
};

class CMap{
private:
    int mCapacity; //容量
    int mCount; //个数
    Node* mNodeArr; //顶点数组
    int* mPMatrix;//邻接矩阵
    Edge* edge; //最小边
public:
    //初始化图
    CMap(int mCapacity) : mCapacity(mCapacity),mCount(0) {
        mNodeArr = new Node[mCapacity]; //节点数组
        mPMatrix = new int[mCapacity*mCapacity];    //邻接矩阵
        memset(mPMatrix,0,mCapacity*mCapacity*sizeof(int)); //初始化空间
        edge = new Edge[mCapacity-1];   //最小边
    }

    //释放资源
    virtual ~CMap() {
        delete [] mNodeArr;
        mNodeArr = nullptr;
        delete [] mPMatrix;
        mPMatrix = nullptr;
        delete [] edge;
        edge = nullptr;
    }
    //添加节点
    bool addNode(Node *node){
        mNodeArr[mCount++].mData = node->mData;
        return true;
    }
    //重置节点访问情况
    void resetNode(){
        for (int i = 0; i < mCount; ++i) {
            mNodeArr[i].mIsVisited = false;
        }
    }

    //为有向图设 置邻接矩阵
    bool setValueToMatrixForDirectedGraph(int row, int col, int val= 1) {
        if (row<0 || row >= mCapacity || col < 0 || col >= mCapacity) return false;
        //mPMatrix[i][j] == mPMatrix[i*mCapacity+j]
        mPMatrix[row*mCapacity+col] = val;
        return true;
    }

    //为无向图设置邻接矩阵
    bool setValueToMatrixForUndirectedGraph(int row, int col, int val= 1) {
        if (row<0 || row >= mCapacity || col < 0 || col >= mCapacity) return false;
        //mPMatrix[i][j] == mPMatrix[i*mCapacity+j]
        mPMatrix[row*mCapacity+col] = val;
        //mPMatrix[j][i] == mPMatrix[j*mCapacity+i]
        mPMatrix[col*mCapacity+row] = val;
        return true;
    }

    //打印邻接矩阵
    void printMatix() {
        for (int i = 0; i < mCapacity; ++i) {
            for (int j = 0; j < mCapacity; ++j) {
                cout<<mPMatrix[i*mCapacity+j] <<" ";
            }
            cout<<endl;
        }
    }
    //深度优先遍历
    void depthFirstTraverse(int nodeIndex) {
        //访问当前节点
        cout<<mNodeArr[nodeIndex].mData<<" ";
        //设置访问过
        mNodeArr[nodeIndex].mIsVisited = true;

        //是否与其他节点有连接
        int value=0;
        for (int i = 0; i < mCapacity; ++i) {
            //判断是否连接
            getValueFromMatrix(nodeIndex,i,value);//取出连接的点权重
            if (value == 1){//如果存在
                if(mNodeArr[i].mIsVisited) continue;//如果访问过，下一个
                else depthFirstTraverse(i); //继续DFS
            }
        }

    }

    //广度优先遍历
    void breadthFirstTraverse(int nodeIndex) {
        //访问当前节点
        cout<<mNodeArr[nodeIndex].mData<<" ";
        mNodeArr[nodeIndex].mIsVisited = true;
        //加入队列
        vector<int> bfs;
        bfs.push_back(nodeIndex);
        //进入广度优先遍历具体实现
        breadthFirstTraverselmp(bfs);
    }

    //Prim 普里姆算法   nodeIndex 指定第一个点
    void primTree(int nodeIndex){
        int value = 0;
        int edgeCount=0;
        vector<int> nodeVec; //点集
        vector<Edge> edgeVec;   //边集

        //打印数据
        cout << mNodeArr[nodeIndex].mData<<endl;

        //加入点集合
        nodeVec.push_back(nodeIndex);
        //设置访问过
        mNodeArr[nodeIndex].mIsVisited = true;

        //最小生成树的边 == 容量 - 1
        while (edgeCount < mCapacity-1){
            //取出最尾部的值
            int tmp = nodeVec.back();
            for (int i = 0; i < mCapacity; ++i) {
                getValueFromMatrix(tmp,i,value);
                if ( value != 0){
                    if (mNodeArr[i].mIsVisited) continue;
                    else{ //加入边
                        Edge edg(tmp,i,value);
                        edgeVec.push_back(edg);
                    }
                }
            }
            //从可选边中找到最小边
            int edgeIndex = getMinEdge(edgeVec);
            if (edgeIndex == -1) continue;
            edgeVec[edgeIndex].bSelected = true;

            //打印数据最小边
            cout << edgeVec[edgeIndex].iNodeIndexA<<" ---"<<edgeVec[edgeIndex].iNodeIndexB<<" " <<edgeVec[edgeIndex].iWeightValue<<endl;

            //加入最小边
            edge[edgeCount++] = edgeVec[edgeIndex];
            //加入新加入的最小边的点
            int nextNodeIndex = edgeVec[edgeIndex].iNodeIndexB;
            nodeVec.push_back(nextNodeIndex);
            //设置访问过
            mNodeArr[nextNodeIndex].mIsVisited = true;

            //打印数据新加入点
            cout << mNodeArr[nextNodeIndex].mData<<endl;

        }

    }

    //取得最小边
    int getMinEdge(vector<Edge> edgeV){
        int minWeight = INT16_MAX; //为了找到最小设置成整形最大
        int edgeIndex = -1;
        for (int i = 0; i < edgeV.size() ; ++i) {
            //如果边没有找到
            if (!edgeV[i].bSelected){
                //找到最小边
                if (minWeight > edgeV[i].iWeightValue) {
                    minWeight = edgeV[i].iWeightValue;
                    edgeIndex = i;
                }
            }
        }
        //返回下标
        return edgeIndex;
    }

    //判断是否在集合中
    bool isInSet(vector<int> &nodeSet, int target) {
        for (int i = 0; i < nodeSet.size(); ++i) {
            if (nodeSet[i] == target){
                return true;
            }
        }
        return false;
    }

    //将B集合元素合并到A集合元素
    void mergeNodeSet(vector<int> &nodeSetA, vector<int> &nodeSetB) {
        for (int i = 0; i < nodeSetB.size(); ++i) {
            nodeSetA.push_back(nodeSetB[i]);
        }
    }

    //克鲁斯卡尔生成树
    void kruskalTree(){

        int value = 0;
        int edgeConut = 0;
        //定义存放节点集合的数组
        vector<vector<int>> nodeSets;
        //step1: 取出所有的边
        vector<Edge> edgeVec;
        for (int i = 0; i < mCapacity; ++i) {
            for (int j = 0; j < i; ++j) {
                getValueFromMatrix(i,j,value);
                if (value != 0){    //加入边集合
                    Edge edg(j,i,value);
                    edgeVec.push_back(edg);
                }
            }
        }

        //step2: 取出组成最小的边

        //1.算法结束条件
        while (edgeConut < mCapacity - 1) {
            //2.找出最小边
            int minEdgeIndex = getMinEdge(edgeVec);
            edgeVec[minEdgeIndex].bSelected = true;
            //3.找出最小连接的点
            int nodeAindex = edgeVec[minEdgeIndex].iNodeIndexA;
            int nodeBindex = edgeVec[minEdgeIndex].iNodeIndexB;
            //4.找出点集合
            bool nodeAIsInSet = false;
            bool nodeBIsInSet = false;
            int nodeAIsInSetLabel = -1;
            int nodeBIsInSetLabel = -1;
            //找到A点所在的集合索引
            for (int i = 0; i < nodeSets.size(); ++i) {
                nodeAIsInSet = isInSet(nodeSets[i],nodeAindex);
                if (nodeAIsInSet){
                    nodeAIsInSetLabel = i;
                }
            }
            //找到A点所在的集合索引
            for (int i = 0; i < nodeSets.size(); ++i) {
                nodeBIsInSet = isInSet(nodeSets[i],nodeBindex);
                if (nodeBIsInSet){
                    nodeBIsInSetLabel = i;
                }
            }
            //5.根据点所在集合做不同处理
            //AB点均不在集合中
            if (nodeAIsInSetLabel == -1 && nodeBIsInSetLabel == -1){
                //创建新集合，加入集合集中
                vector<int> vec;
                vec.push_back(nodeAindex);
                vec.push_back(nodeBindex);
                nodeSets.push_back(vec);
            } else if (nodeAIsInSetLabel == -1 && nodeBIsInSetLabel != -1){ // A点不在集合中，B点在集合中
                nodeSets[nodeBIsInSetLabel].push_back(nodeAindex); //加入B点集合
            } else if (nodeAIsInSetLabel != -1 && nodeBIsInSetLabel == -1){ // B点不在集合中，A点在集合中
                nodeSets[nodeAIsInSetLabel].push_back(nodeBindex); //加入A点集合
            } else if(nodeAIsInSetLabel != -1 && nodeBIsInSetLabel != -1 && nodeAIsInSetLabel != nodeBIsInSetLabel){ //相等的情况
                //将B集合元素合并到A集合元素
                mergeNodeSet(nodeSets[nodeAIsInSetLabel],nodeSets[nodeBIsInSetLabel]);
                //将B集合删除
                nodeSets.erase(nodeSets.begin()+nodeBIsInSetLabel);
            } else continue;
            //加入最小边
            edge[edgeConut++] = edgeVec[minEdgeIndex];
            //打印测试数据
            cout<< edgeVec[minEdgeIndex].iNodeIndexA<< " -- "<<edgeVec[minEdgeIndex].iNodeIndexB<<" "<<edgeVec[minEdgeIndex].iWeightValue<<endl;
        }
    }

private:
    bool getValueFromMatrix(int row, int col, int &val) {  //从矩阵中获取权值
        if (row<0 || row >= mCapacity || col < 0 || col >= mCapacity) return false;
        val = mPMatrix[row * mCapacity +col];
        return true;
    }
    void breadthFirstTraverselmp(vector<int> preVec) {  // 广度优先遍历实现的数
        int val = 0;
        vector<int> bfs;
        for (int i = 0; i < (int) preVec.size(); ++i) {
            for (int j = 0; j < mCapacity; ++j) {
                getValueFromMatrix(preVec[i],j,val);
                if (val !=0){
                    if(mNodeArr[j].mIsVisited) continue;//如果访问过，下一个
                    else { //访问 BFS
                        cout<<mNodeArr[j].mData<<" ";
                        mNodeArr[j].mIsVisited = true;
                        //加入当前访问的值
                        bfs.push_back(j);
                    }
                }
            }
        }

        if (bfs.size() == 0) return;
        //进入下一层
        breadthFirstTraverselmp(bfs);
    }


};
#endif //DATAORGANIZATION_CMAPBASE1_H
